package generate_parentheses

var ans []string

func generateParenthesis(n int) []string {
	ans = make([]string, 0)
	helper("", n, n)
	return ans
}

func helper(str string, left, right int) {
	if left == 0 && right == 0 {
		ans = append(ans, str)
		return
	}
	if left == right {
		//剩余左右括号数相等，下一个只能用左括号
		helper(str+"(", left-1, right)
	} else if left < right {
		//剩余左括号小于右括号，下一个可以用左括号也可以用右括号
		if left > 0 {
			helper(str+"(", left-1, right)
		}
		helper(str+")", left, right-1)
	}
}
